Linked List

연결 리스트(Linked List)
선형적 순서가 결정되는 배열과 달리 각 객체에 있는 포인터에 의해 순서가 결정된다.

- 양방향 연결 리스트(Doubly Linked List)
각 객체 L은 원소 key속성값과 두 개의 포인터 prev, next를 속성값으로 가진다.

x.prev=NIL인 원소 x를 Head라고 함
x.next=NIL인 원소 x를 Tail라고 함

속성값 L.head는 첫 번째 원소를 가리킨다.
List가 empty인 경우 L.head=NIL

- 단순 연결 리스트(Singley Linked List)
양방향 연결 리스트에서 prev 포인터가 제외된 리스트
- 환형 연결 리스트(Circular Linked List)
리스트 머리의 prev 포인터는 리스트의 꼬리를, 리스트의 꼬리의 next 포인터는 리스트의 머리를 가르킴.
- 정렬된 or 정렬되지 않은 리스트
List가 key값의 크기로 정렬되어 있는지 유무에 따른 구분
비정렬 양방향 연결 리스트
#include <iostream>
template <typename T>
struct ListNode{
T data;
ListNode* prev=nullptr;
ListNode* next;
ListNode(T _data, ListNode* _next): data(_data), next(_next){}
~ListNode(){};
};
template <typename T>
struct List{
ListNode<T>* head=nullptr;
ListNode<T>* cur;
List(){}
~List(){}
void Insert(T data){
this->cur=new ListNode<T>(data, this->head);
if(this->head!=nullptr){
this->head->prev=this->cur;
}
this->head=this->cur;
}
ListNode<T>* Search(T key){
this->cur=this->head;
while(this->cur!=nullptr && this->cur->data!=key){
this->cur=this->cur->next;
}
return this->cur;
}
void Delete(ListNode<T>* x){
if(x->prev!=nullptr) x->prev->next=x->next;
else this->head=x->next;
if(x->next!=nullptr) x->next->prev=x->prev;
delete x;
}
};
int main(void){
List<int> list;
list.Insert(10);
list.Insert(5);
list.Insert(1);
list.Insert(3);
list.Insert(6);
list.Delete(list.Search(6));
return 0;
}
위의 코드는 경계(head) 때문에 과정이 상당히 복잡하다.
일반적으로 경계 원소를 포함하는 환형 양방향 연결 리스트(Circular, doubly linked list with a sentinel)
로 구현하면, 더 간단하게 구현할 수 있다.
Circular, doubly linked list with a sentinel
#include <iostream>
template <typename T>
struct ListNode{
T data;
ListNode* prev=nullptr;
ListNode* next;
ListNode(T _data, ListNode* _next): data(_data), next(_next){}
~ListNode(){};
};
template <typename T>
struct List{
ListNode<T>* nil;
ListNode<T>* cur;
List(){
this->nil=new ListNode<T>(0, nullptr);
this->nil->next=this->nil;
this->nil->prev=this->nil;
}
~List(){}
void Insert(T data){
this->cur=new ListNode<T>(data, this->nil->next);
this->nil->next->prev=this->cur;
this->nil->next=cur;
this->cur->prev=this->nil;
}
ListNode<T>* Search(T key){
this->cur=this->nil->next;
while(this->cur!=this->nil && this->cur->data!=key){
this->cur=this->cur->next;
}
return this->cur;
}
void Delete(ListNode<T>* x){
x->prev->next=x->next;
x->next->prev=x->prev;
delete x;
}
};
int main(void){
List<int> list;
list.Insert(10);
list.Insert(5);
list.Insert(1);
list.Insert(3);
list.Insert(6);
list.Delete(list.Search(6));
return 0;
}
경계 원소를 사용함을 통해서 점근적 수행시간을 줄이기를 기대하기는 힘들지만,
코드의 명확성이란 이점에서 많이 채택된다.
Optimized Linked List
struct Node{
int data;
Node* ptrdiff // x.prev^x.next
Node* Prev(Node* next){
return (Node*)((long long int)this->ptrdiff ^ (long long int)next);
}
Node* Next(Node* prev){
return (Node*)((long long int)this->ptrdiff ^ (long long int)prev);
}
};